package algorithm.dynamicProgramming;

import java.util.Arrays;

/**
 * @Author CandyWall
 * @Date 2021/4/6--9:41
 * @Description 0-1背包问题
 *                  动态规划解法
 */
public class Knapsack01_v2 {
    /**
     *
     * @param w ：物品的重量
     * @param v ：物品的价值
     * @param c ：背包的剩余容量
     * @return
     */
    public int fillKnapsack(int[] w, int[] v, int c) {
        if (w.length != v.length) {
            throw new IllegalArgumentException("记录物品的重量和价值的数组长度不一致！");
        }
        int n = w.length;
        if (n == 0) {
            return 0;
        }
        // 初始化memo数组
        int[][] memo = new int[n][c + 1];
        // 只考虑第0个物品，计算随着背包容量的改变，背包中的物品价值
        for (int j = 0; j <= c; j++) {
            memo[0][j] = j >= w[0] ? v[0] : 0;
        }
        for (int i = 1; i < n; i++) {
            Arrays.fill(memo[i], -1);
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= c; j++) {
                memo[i][j] = Math.max(memo[i - 1][j], (w[i] <= j ? v[i] + memo[i - 1][j - w[i]] : 0));
            }
        }

        return memo[n - 1][c];
    }

    public static void main(String[] args) {
        System.out.println(new Knapsack01_v2().fillKnapsack(new int[]{1, 2, 3}, new int[]{6, 10, 12}, 5));
    }
}
